The present invention concerns a coding device, a coding method, a decoding device and method and systems using them.
It applies equally well to the coding of data representing a physical quantity, to the coding of data in the form of codes capable of modulating a physical quantity, to the decoding of data-modulated signals, and to the decoding of data representing physical quantities. These data can, for example, represent images, sounds, computer data, electrical quantities or stored data.
The invention finds an application in the field of convolutional codes. When the latter are used to implement an iterative decoding, these codes are greatly improved when their coders contain a permutation device. In this case, they are usually referred to as xe2x80x9cturbocodesxe2x80x9d and the corresponding iterative decoder is referred to as a xe2x80x9cturbodecoderxe2x80x9d. For convenience:
the operation performed by the turbocoder is referred to as xe2x80x9cturbocodingxe2x80x9d and this operation provides a so-called xe2x80x9cturbocodedxe2x80x9d sequence, and
the operation performed by the decoder is referred to as xe2x80x9cturbodecodingxe2x80x9d and this operation provides a so-called xe2x80x9cturbodecodedxe2x80x9d sequence.
On these subjects, documents which serve as a reference are, on the one hand, the article by Messrs. C. BERROU, A. GLAVIEUX and P.
THITIMAJSHIMA entitled xe2x80x9cNear Shannon limit error-correcting coding and decoding: turbocodesxe2x80x9d published with the reports of the xe2x80x9cICC""93xe2x80x9d conference, 1993, pages 1064 to 1070, and on the other hand, the article by Messrs. C. BERROU and A. GLAVIEUX entitled xe2x80x9cNear Optimum error-correcting coding and decoding: turbo-codesxe2x80x9d published by IEEE Transactions on Communication, Volume COM-44, pages 1261 to 1271, in October 1996.
However, the formation of permutation devices is far from being completely mastered. Certain of these devices use square or rectangular matrices which are written into one row after another and read from one column after another. These matrices are generally very large, for example 256xc3x97256 in size.
A parallel turbocoder of efficiency equal to ⅓ can be considered as a pair of convolutional systematic recursive coders with divisor polynomials such that the first coder produces a check sequence from the sequence of symbols to be coded u and the second coder produces a check sequence from an interleaved sequence u* obtained by interleaving (or xe2x80x9cpermutationxe2x80x9d) of the sequence u. In this context, the simultaneous return to zero of the two coders is a classic problem. One way of solving it has been found by the inventors and is summarized below.
With the aim of clarity, it will be assumed, subsequently, that the two divisor polynomials of the turbocoder are equal and referred to as g(x). Let m be the degree of the polynomial g(x) and let N0 be the smallest integer such that g(x) is a divisor of the polynomial xN0+1. For reasons described below, a polynomial g(x) is chosen having no divisor which is the square of a polynomial of degree equal to or greater than 1, and this leads to N0 being an odd number.
Also let n be an odd multiple of N0: n=M N0.
A sequence of symbols, u, then has a polynomial representation u(x), of degree nxe2x88x92mxe2x88x921, with binary coefficients, and this polynomial u(x) is precoded into:
a(x)=u(x)+xcexa3i=nxe2x88x92m to nxe2x88x921aixi
where the m binary symbols ai are chosen in such a way that a(x) is a multiple of g(x). As a consequence of this preceding and the chosen values of the parameters, if a(x) is a multiple of g(x), then a*(x)=a(xe) modulo xn+1 is also a multiple of g(x) for any value of e which is a power of 2.
In the remainder of the description, the permutation and interleaver type described above is referred to as xe2x80x9cx to xexe2x80x9d.
Here, it is necessary to consider that g(x) has no multiple factor since, in general, a*(x) is guaranteed to be divisible only by the irreducible factors of g(x).
The coded version of u is then given by v=[a, ah1/g, a*h2/g], where all the components are polynomials, and where, in particular, a*h2/g is also a polynomial, by virtue of the definition of a* and the choice of e as a power of 2.
With general turbocodes, the decoding is essentially an iterative procedure (on this subject see the document by Messrs. BERROU and GLAVIEUX, xe2x80x9cNear optimum error-correcting and decoding: turbocodesxe2x80x9d, IEEE Trans. On Comm., Vol. COM-44, pages 1261 to 1271, October 1996).
The document by J. ANDERSEN is known, xe2x80x9cTurbocoding for deep space applicationsxe2x80x9d, proceedings IEEE 1995, International Symposium on Information Theory, Whistler, Canada, September 1995, in which a BCH code is used for correcting the residual errors. However, this solution has a fairly limited effectiveness in terms of residual error bit correction. The inventors observed that this last remark was particularly true in the case of the use of xe2x80x9cx to xexe2x80x9d type interleavers.
The present invention aims to remedy these drawbacks. To this end, the present invention relates, according to a first aspect, to a method of coding a sequence of information symbols of polynomial representation u(x), including:
a turbocoding operation, and
an operation of transmitting, on a transmission channel, the sequence resulting from the turbocoding operation,
characterised in that it also includes, as a preliminary to the said turbocoding operation, at least one precoding operation during which there are added, to the said sequence u(x), redundant symbols which guarantee the divisibility of the precoded sequence by at least one predetermined polynomial which is:
a non-trivial multiple of the divisor polynomial used by the coder of the said turbocoder, a coder which acts on the precoded sequence, and
which is among the polynomials which have a high probability of dividing the polynomial representing a transmission error on the said channel.
The present invention relates, according to a second aspect, to a decoding method, characterised in that it takes into account:
at least one predetermined polynomial, and
a received sequence r capable of being the result of the coding of a sequence of information symbols of polynomial representation u(x) representing a physical quantity, the coding including a turbocoding, and guaranteeing the divisibility of a sequence to be turbocoded, a(x) representing the sequence u(x), by each predetermined polynomial,
and in that it includes:
an operation of turbodecoding the received sequence r into an estimated sequence xc3xa2,
at least one operation of calculating the remainder of the division of the polynomial representation xc3xa2(x) of the estimated sequence xc3xa2, by a said predetermined polynomial.
The inventors, in fact, observed that the residual errors have, in the case described above (xe2x80x9cx to xexe2x80x9d), a particular structure as far as the iterations of the decoder are continued until their result stabilizes. This particular structure makes them, generally, divisible by one or more predetermined polynomials.
The present invention aims to make use of this observation by proposing a method for detection or correction of these residual errors which is well adapted to the coding scheme described above.
By virtue of the provisions of the present invention, the processing (detection or correction) of residual errors, after turbodecoding, can be performed, on the one hand, on the received sequence and, on the other hand, on the sequence resulting from the division operation. The implementation of the method of the present invention is therefore particularly simple.
For example, the information sequence u(x) is precoded into a polynomial a(x)=u(x)+xcexa3i=nxe2x88x92m to nxe2x88x921 aixi, so that the sequence a(x) is a multiple, not only of the divisor polynomial of the turbocode, but also of other predetermined polynomials and of a generator polynomial denoted by q(x) of a binary BCH code, or more generally of a binary cyclic code, in length at least equal to n, and correcting s errors, where s is for example chosen equal to four.
This particular precoding necessitates a value of m higher than the degree of g(x). Consequently, at fixed n, the degree nxe2x88x92mxe2x88x921 of the polynomials u(x) representing the information is reduced in an adapted manner. By virtue of these provisions, processing for detection or correction of residual errors after turbodecoding can be performed, not only on the turbodecoded sequence, denoted by xc3xa2, but also on the sequence or sequences obtained by dividing xc3xa2 by each of the said predetermined polynomials, each time this division is possible with no remainder.
After having been decoded into a word of the BCH code under consideration, each of the said sequences is multiplied by the predetermined polynomial corresponding to it.
Thus, the sequences resulting from the multiplication operation can be compared in order to determine the final estimate of the information sequence transmitted.
The advantage of this method is that, if the predetermined polynomials are well chosen, the residual error after turbodecoding is often divisible by one or more of these predetermined polynomials, and that, for at least one of these predetermined polynomials, the weight of the error after division is smaller than it was before division.
Thus, the residual errors after turbodecoding can be corrected although initially their weight is too high to allow correction by the BCH code or, more generally, by the cyclic code.
It should be noted here that the decoding method in accordance with the present invention can operate in relation with coding methods of the prior art, and, in particular, with those which use so-called xe2x80x9cpaddingxe2x80x9d operations which guarantee the divisibility of a sequence to be turbocoded by a divisor polynomial of the said turbocoder.
According to particular characteristics, during an operation of calculating the remainder of the division of the polynomial representation of the estimated sequence xc3xa2, the predetermined polynomial is a divisor polynomial of a coder of the said turbocoder, a coder which acts on the sequence a(x).
By virtue of these provisions, the effect of the invention is obtained, at least partially, without supplementary addition of redundancy to the information sequence to be transmitted.
According to other particular characteristics, the decoding method as briefly described above includes an error detection operation during which:
it is determined whether or not the remainder from the said division remainder calculation operation is null, and,
where this remainder is not null, an error is detected.
By virtue of these provisions, the error detection is particularly easy.
The present invention relates, according to a third aspect, to a decoding device, characterised in that it has a processing means adapted:
A/ to take into account:
at least one predetermined polynomial, and
a received sequence r capable of being the result of the coding of a sequence of information symbols of polynomial representation u(x) representing a physical quantity, the coding including a turbocoding, and guaranteeing the divisibility of a sequence to be turbocoded, a(x) representing the sequence u(x), by each predetermined polynomial, and
B/ to turbodecode the received sequence r into an estimated sequence xc3xa2, and
C/ to calculate the remainder of the division of the polynomial representation xc3xa2(x) of the estimated sequence xc3xa2, by each said predetermined polynomial.
The present invention relates, according to a fourth aspect, to a device for coding a sequence of information symbols of polynomial representation u(x), having:
a processing means adapted to turbocode, and
a means of transmitting, on a transmission channel, the sequence resulting from the turbocoding,
characterised in that the processing means is adapted, as a preliminary to the turbocoding, to precode the said sequence u(x), adding redundant symbols thereto which guarantee the divisibility of the precoded sequence by at least one predetermined polynomial which is:
a non-trivial multiple of the divisor polynomial used by the coder of the said turbocoder, a coder which acts on the precoded sequence, and
which is among the polynomials which have a high probability of dividing the polynomial representing a transmission error on the said channel.
The invention also relates to:
an information storage means readable by a computer or a microprocessor storing instructions of a computer program, characterised in that it allows the implementation of the method of the invention as briefly described above, and
an information storage means which is removable, partially or totally, and readable by a computer or a microprocessor storing instructions of a computer program, characterised in that it allows the implementation of the method of the invention as briefly described above.
The invention also relates to:
a device for receiving transmitted data having a receiver adapted to use a packet transmission protocol, which has a decoding device as briefly described above;
a device for receiving transmitted data having a receiver adapted to use the ATM (xe2x80x9cAsynchronous Transfer Modexe2x80x9d) packet transmission protocol, which has a decoding device as briefly described above;
a device for receiving transmitted data having a receiver adapted to use the packet transmission protocol, on an ETHERNET (registered trade mark) type network, which has a decoding device as briefly described above;
a network station, which has a decoding device as briefly described above;
a device for receiving transmitted data having a receiver for signals transmitted on a wireless channel, which has a decoding device as briefly described above;
a data transmission device having a transmitter adapted to use a packet transmission protocol, which has a coding device as briefly described above;
a data transmission device having a transmitter adapted to use the ATM (xe2x80x9cAsynchronous Transfer Modexe2x80x9d) packet transmission protocol, which has a coding device as briefly described above;
a data transmission device having a transmitter adapted to use a packet transmission protocol, on an ETHERNET (registered trade mark) type network, which has a coding device as briefly described above;
a device for transmitting data of any type including notably speech, image or multimedia type data, having a transmitter of signals transmitted on a wireless channel, which has a coding device as briefly described above.
This decoding device, this coding device, these storage means, these data receiving devices, these data transmission devices and this network having the same particular characteristics and the same advantages as the coding method as briefly described above, these particular characteristics and these advantages are not repeated here.